package _go

/*22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

有效括号组合需满足：左括号必须以正确的顺序闭合。



示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]


提示：

1 <= n <= 8*/
func generateParenthesis(n int) []string {
	if n < 1 {
		return []string{}
	}
	res := []string{}

	//在内部直接减少返回的结果的空间
	//函数参数定义 左括号已使用的数量 右括号已使用的数量 总数量 能拼出来的结果
	var gen func(left, right, n int, str string)
	gen = func(left, right, n int, str string) {
		//如果都用完了 直接把结果写入
		if left == n && right == n {
			res = append(res, str)
			return
		}
		//还有左括号 直接写入
		if left < n {
			gen(left+1, right, n, str+"(")
		}

		//还有右括号 需要判断一下是不是已经有左括号写入了  不能直接写入右括号
		if right < left {
			gen(left, right+1, n, str+")")
		}
	}

	gen(0, 0, n, "")

	return res
}
